package cc.magicjson.example.demo.tsp;

public class GreedyTSP {
	private int[][] dist; // 距离矩阵
	private boolean[] visited; // 标记每个城市是否已被访问
	private int n; // 城市的数量

	public GreedyTSP(int[][] dist) {
		this.dist = dist; // 初始化距离矩阵
		this.n = dist.length; // 获取城市的数量
		this.visited = new boolean[n]; // 初始化访问标记数组
	}

	// 贪心算法求解TSP问题
	public int findShortestPath() {
		int length = 0; // 初始化路径长度
		int currentCity = 0; // 从城市0开始
		visited[0] = true; // 标记城市0已访问

		// 遍历n-1次，每次选择最近的未访问城市
		for (int i = 1; i < n; i++) {
			int nextCity = -1; // 下一个要访问的城市
			int shortestDistance = Integer.MAX_VALUE; // 初始化最短距离为最大值

			// 找到最近的未访问城市
			for (int j = 0; j < n; j++) {
				if (!visited[j] && dist[currentCity][j] < shortestDistance) { // 如果城市j未访问且距离更短
					shortestDistance = dist[currentCity][j]; // 更新最短距离
					nextCity = j; // 更新下一个访问的城市
				}
			}

			// 检查是否找到合适的nextCity
			if (nextCity == -1) {
				throw new RuntimeException("无法找到下一个未访问的城市。这可能意味着输入数据有误或城市之间不连通。");
			}

			visited[nextCity] = true; // 标记下一个城市已访问
			length += shortestDistance; // 增加路径长度
			currentCity = nextCity; // 移动到下一个城市
		}

		// 最后返回起点，完成环路
		length += dist[currentCity][0];
		return length; // 返回总路径长度
	}

	public static void main(String[] args) {
		int[][] dist = {
				{0, 10, 15, 20},  // 城市间的距离矩阵
				{10, 0, 35, 25},
				{15, 35, 0, 30},
				{20, 25, 30, 0}
		};

		GreedyTSP greedyTSP = new GreedyTSP(dist); // 创建贪心算法实例
		System.out.println("贪心算法计算的路径长度: " + greedyTSP.findShortestPath()); // 输出计算结果
	}
}
